package main

import (
	"fmt"
	"math/rand"
)

// 快速排序（Quick Sort）是一种高效的排序算法，采用分治法（Divide and Conquer）策略来对数组进行排序。其基本思想可以分为以下几个步骤：
// 选择基准（Pivot）：
// 从数组中选择一个元素作为基准。选择基准的方法有多种，常见的有选择第一个元素、最后一个元素、随机选择一个元素或选择中间位置的元素。
// 分区（Partitioning）：
// 重新排列数组，使得所有比基准小的元素放在基准的左边，所有比基准大的元素放在基准的右边。此时，基准元素处于其最终位置。
// 递归排序子数组：
// 递归地对基准左边的子数组和右边的子数组进行快速排序。
// 合并：
// 由于快速排序是在原地进行的（即不需要额外的存储空间），因此不需要显式的合并步骤。递归调用完成后，整个数组就已经排序好了。
func main() {

	//最坏情况下，快速排序的时间复杂度为 O(n^2)。
	//最好情况下，快速排序的时间复杂度也为 O(n log n)。
	slice := genSlice(100)
	fmt.Println(*slice)
	QuickSortMinToMax(0, len(*slice)-1, slice)
	fmt.Println(*slice)
}

/*
*
生成一个切片
*/
func genSlice(n int) *[]int {
	var arr []int = make([]int, n)
	for i := 0; i < n; i++ {
		arr[i] = rand.Intn(999)
	}
	return &arr
}

// QuickSortMinToMax 函数实现快速排序
func QuickSortMinToMax(left int, right int, array *[]int) {
	if left >= right {
		return
	}

	l := left
	r := right
	pivot := (*array)[(left+right)/2]

	// 目标：将比 pivot 小的元素放在左边，比 pivot 大的元素放在右边
	for l <= r {
		// 从左边开始找比 pivot 大的元素
		for l <= r && (*array)[l] < pivot {
			l++
		}
		// 从右边开始找比 pivot 小的元素
		for l <= r && (*array)[r] > pivot {
			r--
		}
		// 本次循环结束
		if l <= r {
			// 交换
			(*array)[l], (*array)[r] = (*array)[r], (*array)[l]
			l++
			r--
		}
	}

	// 向左递归
	if left < r {
		QuickSortMinToMax(left, r, array)
	}
	// 向右递归
	if l < right {
		QuickSortMinToMax(l, right, array)
	}
}
